package cn.edu.zzuli.sort;

import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        //基数排序
        int[] arr = {53, 3, 542, 748, 14, 214};

        //定义一个二维数组用来表示10个桶，分别是0-9,列坐标为存入的值
        //其实这个用队列（链表）来做会更好。
        int[][] bucket = new int[10][arr.length];

        //为了确定每个桶数组存放多少数据，我们不得不搞一个一维数组来记录下个数
        int[] bucketCount = new int[10];

        //在排序之前我们还必须找到最大的数到底是几位
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int maxLenth = (max + "").length();

        //接下来我们要进行桶排序了
        for (int i = 0, n = 1; i < maxLenth; i++, n*=10) {
            for (int j = 0; j < arr.length; j++) {
                //找出位数上的数值
                int digit = arr[j] / n % 10;
                //放入到对应的桶中,桶的有效位数+1
                bucket[digit][bucketCount[digit]++] = arr[j];

            }

            //然后将桶中的值依次取出来，放入到arr中
            //用来代表 arr 的下标
            int index = 0;
            for (int j = 0; j < bucketCount.length ; j++) {
                //如果等于0我们根本无需遍历
                if (bucketCount[j] != 0) {
                    for (int k = 0; k < bucketCount[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                }
                //记得将桶的有效位下标给清空
                bucketCount[j] = 0;
            }

        }

        System.out.println(Arrays.toString(arr));

    }

}
